by Arthur Ed LeBouthillier

This article appeared in the April 1999 issue of The Robot Builder.

There are many different programming techniques which one uses only infrequently. One technique, however, can be used repeatedly and regularly: the State Machine.

State machines represent one of the most fundamental principles of computing and programming. They represent the fact that a system can exist in certain states and can transition from one state to another. The state machine is so universal of a concept that virtually all computing can be modeled by state machines. Everything from computers to the very programs that run on them are state machines.

State machines are very important in all aspects of the design of programs. They help gather your thoughts on a topic by providing a notation to represent many complicated interacting states. They also permit you to organize those thoughts into a coherent plan of action. Finally, because they are so easy to implement in code, knowing how to represent your problem as a state machine provides an immediate means to implementing them.

Introduction

A State Machine can be viewed as being composed of nodes representing possible states and conditional transitions between state nodes. Therefore, to represent a state machine, we use state nodes which represent each particular state and conditional transitions between them:

In figure 1, a state machine is shown for a simple robot’s motion. The state machine consists of three states: FWD, for forward motion; BCK, for backward motion; and TRN for turning. There is one entry transition pointing to the FWD state and four conditional transitions between each of the three possible states. A robot controlled by this state machine would enter into the FWD (or forward) state. If a bumper switch was hit, then the robot
would transition to the BCK state and stay there as long as the time variable was less than 2 seconds.

After 2 seconds at the BCK state, the state machine would transition to the TRN state, stay there for 2 seconds and then transition to the FWD state again, starting the whole cycle over. This state machine, although very simple, is representative of the state machine idea.

Using State Machines in the Conceptual Stage

State machine can help simplify the design of programs because they provide an easy notation for what is going on inside your robot. Gather together
the different actions that might occur and call them the states. Gather a list of situations which would cause the system to transition from one state to
another. In some cases, you will find that certain states don’t belong together and that you might have different state machines instead of the one that
you originally thought you had. It is possible to use multiple state machines that enable each other. Using the state machine in figure 1, we might have other state machines which are enabled in each of the three states above. For example, while going forward, we might beep and go forward. While backing up, we might beep, flash a light and then back up. While turning we might flash the lights. The way this would be implemented is by having a total of four state machines, of which the operation of three are controlled by the state machine above. This is illustrated in figure 2. The
double circles with the “End” name are the final states of each state machine. When each state machine enters this state, it does not leave.

Implementing State Machines

Implementing state machines once you have the state machine diagrams is easy. For each state machine that is active, you need a variable to represent its state. In the above example, we would only need 2 variables to keep track of the state

 machines since only the main and one substate is active at a time. State machines are usually implemented as “switch” or “select” statements (depending on the language you are using) inside of a continuous while loop. Assign a number to each state in each state machine. You can restart at 0 for each different state machine. A simple program to implement the state machine above is illustrated in Figure 3. You can put “action” code, or the code that is necessary to perform the state’s action at the conditional statement used to set up the transition.

Conclusion

The state machine concept is very powerful and helps you both in the design and implementation stages of your program. It helps you organize many
complicated events and conditions by providing a notation to detail your program’s operation. It also has a very simple implementation structure which can be duplicated  in every implementation.

Const FWD = 0
Const BCK = 1
Const TRN = 2
Dim MainState as integer
Dim SubState as integer
Dim theTime as integer
MainState = FWD
SubState = 0
Beep
SendMotors( FORWARD )
while TRUE
   select case MainState
   case FWD
      select case SubState
      case 0
         Beep
         SubState = 1
      case 1
         SendMotors(FORWARD)
         SubState = 2
      case 2
         SubState = 2
      end select
      if( bumper = 1)
         theTime = Now()
         SubState = 0
         MainState = BCK
      end if
   case BCK
      select case SubState
         case 0
            Beep
            SubState = 1
         case 1
            FlashLights()
            SubState = 2
         case 2
            SendMotors(BACKWARD)
            SubState = 3
         case 3
            SubState = 3
      end select
      if( DiffTime(theTime,Now()) > 2 )
         theTime = Now()
         SubState = 0
         MainState = TRN
      end if
   case TRN
      select case SubState
         case 0
            Beep
            SubState = 1
         case 1
            SendMotors(RIGHT)
            SubState = 2
         case 2
            FlashLights()
            SubState = 2
       end select
       if( DiffTime(theTime,Now()) > 2)
          SubState = 0
          MainState = FWD
       end if
    end select
end while
Figure 3 - Code for state machine in  figure 2.